# LeetCode 685. 冗余连接 II
# https://leetcode.cn/problems/redundant-connection-ii/description/
import copy
from typing import List


class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = 0
        for edge in edges:
            n = max(n, max(edge))

        parents = [i for i in range(n)]
        size = [1 for i in range(n)]
        adj = {i: [] for i in range(n)}
        in_degrees = {i: 0 for i in range(n)}
        out_degrees = {i: 0 for i in range(n)}

        for edge0, edge1 in edges:
            edge0 -= 1
            edge1 -= 1
            adj[edge1].append(edge0)
            in_degrees[edge1] += 1
            out_degrees[edge0] += 1

        def find(x):
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]

        def union(x, y):
            y_c = copy.deepcopy(y)
            x = find(x)
            y = find(y)
            if y_c != y:
                return False, y_c
            if x == y:
                return True, None
            parents[y] = x
            size[x] += size[y]
            return False, None

        circle = False
        circle_edge = [None, None]
        two_indegree_node = None
        for edge0, edge1 in edges:
            edge0 -= 1
            edge1 -= 1
            flag, node_tmp = union(edge0, edge1)
            if flag:
                circle = True
                circle_edge = [edge0 + 1, edge1 + 1]
            if node_tmp is not None:
                two_indegree_node = node_tmp

        if circle:
            if two_indegree_node is not None:
                parent = find(two_indegree_node)
                for index, p in enumerate(parents):
                    if p == parent and index in adj[two_indegree_node]:
                        return [index + 1, two_indegree_node + 1]
            else:
                return circle_edge

        if two_indegree_node is not None:
            result = (0, [0, 0])
            for v in adj[two_indegree_node]:
                if in_degrees[v] == 0 and out_degrees[v] - 1 == 0:
                    continue
                tmp = [v + 1, two_indegree_node + 1] if [v + 1, two_indegree_node + 1] in edges else [two_indegree_node + 1, v + 1]
                tmp_index = edges.index(tmp)
                if tmp_index >= result[0]:
                    result = (tmp_index, tmp)
            if result != (0, [0, 0]):
                return result[1]


if __name__ == '__main__':
    edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
    # edges = [[2,1],[3,1],[4,2],[1,4]]
    edges = [[5,2],[5,1],[3,1],[3,4],[3,5]]
    edges = [[4,2],[1,5],[5,2],[5,3],[2,4]]
    print(Solution().findRedundantDirectedConnection(edges))
